package com.zhupf.binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhupf
 * @date 2023年12月07日 11:26
 * @Description
 * 437. 路径总和 III
 */
public class PathSum {

    public static void main(String[] args) {
        TreeNode root = new TreeNode();
    }

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long,Integer> map = new HashMap<>();
        map.put(0L,1);
        return process(root,targetSum,0L,map);

    }

    public int process(TreeNode root, int targetSum,Long preSum,Map<Long,Integer> map){
        int res = 0;
        if(root == null){
            return res;
        }
        Long sum = preSum+root.val;
        if(map.containsKey(sum-targetSum)){
            res +=map.get(sum-targetSum);
        }
        if(!map.containsKey(sum)){
            map.put(sum,1);
        }else {
            map.put(sum,map.get(sum)+1);
        }
        res += process(root.left,targetSum,sum,map);
        res += process(root.right,targetSum,sum,map);
        if(map.get(sum) == 1){
            map.remove(sum);
        }else {
            map.put(sum,map.get(sum)-1);
        }
        return res;
    }



}
